package us.kg.kotoriforest.leetcode.hot100;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/path-sum-ii/">113. 路径总和 II</a>
 *
 * @author Kotori rotroutine@163.com
 * @since 2025/1/26
 */
public class PathSum2 {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ans;
    }

    private void dfs(TreeNode root, int targetSum) {
        if (null == root) return;

        targetSum -= root.val;
        path.add(root.val);

        if (root.left == root.right && 0 == targetSum) {
            ans.add(new ArrayList<>(path)); // 拷贝一份
        }

        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.removeLast();
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(5,
                new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));

        System.out.println(pathSum(root, 22));
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

